package com.heima.datastructure.queue;

import java.util.Iterator;

/**
 * <h3>用环形数组实现队列，方法三：head和tail不用来记录索引，只管加一，需要时再算出来，考虑指针到会越界，int表示不了，除数为2^n,公式：被除数 & (除数 - 1) == 余数</h3>
 * @param <E>
 */
public class ArrayQueue3<E> implements Queue<E>, Iterable<E>{
    // 1、head和tail是从0开始的，而且每次入队或者出队都是只加一，所以tail - head就是队列的长度，
    //    那么如果队列为空，则tail - head == 0，如果队列为满，则tail - head == capacity
    //    这里的数组可以全部都用来存队列
    // 2、对于求模运算来说，如果除数是2的n次方，那么商和余数就是被除数的两个部分，其中被除数的
    //    后n位是余数，其余为商，因为除以2的n次方等同于被除数右移n位，移出来的就是余数，留下的
    //    是商。
    // 3、那么除数是2的n次方，怎么算出余数呢？由已知余数就是被除数的后n位，也就是需要把其他位变
    //    成0，这n位不变，那么就可以把其他位分别和0进行按位与运算，这n位分别和1进行与运算，也就
    //    是把被除数与n个1的二进制数进行与运算，这n个1的二进制数恰好又是2^n - 1，也就是除数 - 1
    // 4、当这个队列进行了频繁的出队入队后，head和tail会变得非常大，int极有可能表示不了，如果
    //    是C语言则用unsigned int即可解决，但是java要稍微复杂一点
    // 5、由已知当除数为2^n时，余数就是被除数的后n位，又当tail++或者head++越界时，int虽然表示不
    //    了，但实际上是舍弃了进位到高位的数据，后面的位影响很小，例如：int的最大值：0x7FFFFFFF，
    //    加一后变成了0x80000000，再一直加到0xFFFFFFFF，这些与理论值相比都是把理论值的第二位当作
    //    了符号位，而其余的数都没变化，如果再继续加，会往前进位，理论值的位数增加，加的越多，理论
    //    值开头就有更多的位被舍弃，如果除数为2^n，n <= 实际值的位数(31，不包括符号位)，那么余
    //    数永远都不会失真，失真的永远只有商，所以即便越界了，后n位依旧是余数
    private E[] arr; // 环形数组
    private int head; // 头指针，对数组长度取余后指向第一个元素
    private int tail; // 尾指针，对数组长度取余后指向最后一个元素的下一个元素

    private int capacity = 8; // 数组的容量，要保证capacity为2^n

    /**
     * 用于测试
     * @param head 头指针
     */
    public void setHead(int head) {
        this.head = head;
    }

    /**
     * 用于测试
     * @param tail 尾指针
     */
    public void setTail(int tail) {
        this.tail = tail;
    }

    /**
     * 用构造器初始化
     * @param capacity
     */
    @SuppressWarnings("all")
    public ArrayQueue3() {
        // 如何判断一个数是否是2^n:(capacity & (capacity - 1)) == 0
        arr = (E[])new Object[capacity];
        head = 0;
        tail = 0;
    }

    /**
     * 队尾插入元素
     * @param value 待插入值
     * @return 插入成功返回true
     */
    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        arr[tail & (capacity - 1)] = value; // 取被除数的后n位
        tail++; // 不用管是否越界
        return true;
    }

    /**
     * 获取队头元素并删除
     * @return 队头元素，不存在返回null
     */
    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        E value = arr[head & (capacity - 1)];
        // 如果是基本类型，不用释放，例如int初始化为0还是四个字节，
        // 但是这里用了泛型，未来会被具体的对象替代，数组里面存的指针（对象的地址），
        // 指针指向这个对象，属于引用类型，该数组元素指向一个对象实例，
        // 当对象实例没有人指向它时才会被垃圾回收，所以这里要去掉指向该对象实例的指针
        arr[head & (capacity - 1)] = null;
        head++;
        return value;
    }

    /**
     * 获取队头元素
     * @return 队头元素，不存在返回null
     */
    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        return arr[head & (capacity - 1)];
    }

    /**
     * 判断队列是否为空
     * @return 为空返回true
     */
    @Override
    public boolean isEmpty() {
        return tail - head == 0;
    }

    /**
     * 判断队列是否为满
     * @return 为满返回true
     */
    @Override
    public boolean isFull() {
        // 即使tail越界，相减不会出错，因为一次自加操作至多改变两位，所以即便越界了，进行一次自加后除了最后两位，其余位都不可能改变
        return tail - head == capacity;
    }

    /**
     * 迭代器
     * @return 迭代器
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = head;
            @Override
            public boolean hasNext() {
                return index != tail;
            }

            @Override
            public E next() {
                E value = arr[index & (capacity - 1)];
                index++;
                return value;
            }
        };
    }

    /**
     * 获取队列大小
     * @return 队列大小
     */
    public int size(){
        return tail - head ;
    }

    /**
     * 扩容，一次扩容乘以2
     * @param capacity 容量
     */
    @SuppressWarnings("all")
    public void expansion(){
        capacity *= 2;
        E[] array = (E[])new Object[capacity];
        int j = 0;
        for (int i = head; i != tail; i++, j++){
            array[j] = arr[i & (capacity - 1)];
        }
        head = 0;
        tail = j;
        arr = array;
    }
}
